{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stamping The Sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #queue #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #队列 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: movesToStamp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #戳印序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你想要用<strong>小写字母</strong>组成一个目标字符串&nbsp;<code>target</code>。&nbsp;</p>\n",
    "\n",
    "<p>开始的时候，序列由&nbsp;<code>target.length</code>&nbsp;个&nbsp;<code>&#39;?&#39;</code>&nbsp;记号组成。而你有一个小写字母印章&nbsp;<code>stamp</code>。</p>\n",
    "\n",
    "<p>在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行&nbsp;<code>10 * target.length</code>&nbsp; 个回合。</p>\n",
    "\n",
    "<p>举个例子，如果初始序列为 &quot;?????&quot;，而你的印章 <code>stamp</code>&nbsp;是&nbsp;<code>&quot;abc&quot;</code>，那么在第一回合，你可以得到&nbsp;&quot;abc??&quot;、&quot;?abc?&quot;、&quot;??abc&quot;。（请注意，印章必须完全包含在序列的边界内才能盖下去。）</p>\n",
    "\n",
    "<p>如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。</p>\n",
    "\n",
    "<p>例如，如果序列是 &quot;ababc&quot;，印章是 <code>&quot;abc&quot;</code>，那么我们就可以返回与操作&nbsp;&quot;?????&quot; -&gt; &quot;abc??&quot; -&gt; &quot;ababc&quot; 相对应的答案 <code>[0, 2]</code>；</p>\n",
    "\n",
    "<p>另外，如果可以印出序列，那么需要保证可以在 <code>10 * target.length</code>&nbsp;个回合内完成。任何超过此数字的答案将不被接受。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>stamp = &quot;abc&quot;, target = &quot;ababc&quot;\n",
    "<strong>输出：</strong>[0,2]\n",
    "（[1,0,2] 以及其他一些可能的结果也将作为答案被接受）\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>stamp = &quot;abca&quot;, target = &quot;aabcaca&quot;\n",
    "<strong>输出：</strong>[3,0,1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= stamp.length &lt;= target.length &lt;= 1000</code></li>\n",
    "\t<li><code>stamp</code> 和&nbsp;<code>target</code>&nbsp;只包含小写字母。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stamping-the-sequence](https://leetcode.cn/problems/stamping-the-sequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stamping-the-sequence](https://leetcode.cn/problems/stamping-the-sequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n\"ababc\"', '\"abca\"\\n\"aabcaca\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        n = len(target)\n",
    "        m = len(stamp) \n",
    "        arr1 = list(target)\n",
    "        arr2 = list(stamp)\n",
    "        ans = []\n",
    "        \n",
    "        while len(ans) < 10 * n:\n",
    "            i = 0 \n",
    "            flag = 0 \n",
    "            pre = 0 \n",
    "            while i < n:\n",
    "                l = 0 \n",
    "                flag1 = 0 \n",
    "                if i <= n-m:\n",
    "                    for j in range(m):\n",
    "                        if arr1[i+j] == '?' or arr1[i+j] == arr2[j]:\n",
    "                            if arr1[i+j] != '?':\n",
    "                                flag1=1 \n",
    "                            l+=1\n",
    "                        else:\n",
    "                            break\n",
    "                if l == m:\n",
    "                    if flag1:\n",
    "                        ans.append(i)\n",
    "                        flag= 1\n",
    "                    for j in range(i, i+l):\n",
    "                        arr1[j] = '?' \n",
    "                    pre = i + 1\n",
    "                    i+= m \n",
    "                elif i > pre and arr1[i-1] == '?':\n",
    "                    i -= 1 \n",
    "                else:\n",
    "                    i = pre + 1\n",
    "                    #i += 1\n",
    "                    pre = i \n",
    "                    while i < n-m and arr1[i] == '?':\n",
    "                        i+=1  \n",
    "                    #i+=1 \n",
    "            #print(ans)       \n",
    "            if flag == 0:\n",
    "                break \n",
    "            \n",
    "        if arr1 == ['?'] * n:\n",
    "            return ans[::-1]\n",
    "        else:\n",
    "            return [] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        def check(i):\n",
    "            nonlocal m \n",
    "            res = False\n",
    "            for j in range(m):\n",
    "                k = i + j \n",
    "                if target[k] != '?':\n",
    "                    if target[k] != stamp[j]:\n",
    "                        return False \n",
    "                    res = True\n",
    "            return res\n",
    "        \n",
    "        target = list(target)\n",
    "        m, n = len(stamp), len(target)\n",
    "        res = []\n",
    "        flag = True \n",
    "        while flag:\n",
    "            flag = False \n",
    "            for i in range(n-m+1):\n",
    "                if check(i):\n",
    "                    flag = True \n",
    "                    res.append(i)\n",
    "                    target[i:i+m] = '?' * m\n",
    "        res = res[::-1]\n",
    "        return res if all(s == '?' for s in target) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        lst=list(target)\n",
    "\n",
    "        def check(p):\n",
    "            return all(lst[p+j]==\"?\" or lst[p+j]==stamp[j] for j in range(len(stamp)))\n",
    "\n",
    "        res=[]\n",
    "        st=set()\n",
    "        while True:\n",
    "            for p in range(len(lst)-len(stamp)+1):\n",
    "                if p not in st and check(p):\n",
    "                    for j in range(p,p+len(stamp)):\n",
    "                        lst[j]=\"?\"\n",
    "                    res.append(p)\n",
    "                    st.add(p)\n",
    "                    break\n",
    "            else:\n",
    "                if lst==[\"?\"]*len(lst):\n",
    "                    return res[::-1]  \n",
    "                else:\n",
    "                    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        lst = list(target)\n",
    "\n",
    "        def check(p):\n",
    "            return all(lst[p+j]==\"?\" or lst[p+j]==stamp[j] for j in range(len(stamp))) and any(lst[p+j]!=\"?\" for j in range(len(stamp)))\n",
    "\n",
    "        res = []\n",
    "        while True:\n",
    "            for p in range(len(lst)-len(stamp)+1):\n",
    "                if check(p):\n",
    "                    for j in range(p,p+len(stamp)):\n",
    "                        lst[j]=\"?\"\n",
    "                    res.append(p)\n",
    "                    break\n",
    "            else:\n",
    "                return res[::-1] if lst==[\"?\"]*len(lst) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        q = deque([target])\n",
    "        n = len(target)\n",
    "        m = len(stamp)\n",
    "\n",
    "        raw = '?' * n\n",
    "\n",
    "        def check(x, i):\n",
    "            j = 0\n",
    "            c = 0\n",
    "            for i in range(i, i + m):\n",
    "                if x[i] == stamp[j]:\n",
    "                    j += 1\n",
    "                elif x[i] == '?':\n",
    "                    j += 1\n",
    "                    c += 1\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            return c < m\n",
    "\n",
    "        path = []\n",
    "\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "\n",
    "            if x == raw:\n",
    "                path.reverse()\n",
    "                return path\n",
    "\n",
    "            for i in range(n - m + 1):\n",
    "                if check(x, i):\n",
    "                    q.append(x[:i] + '?' * m + x[i + m:])\n",
    "                    path.append(i)\n",
    "                    break\n",
    "\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        # 逆向思考，从target转成'???'，每次选择一个可以的字符串进行转换，拓扑排序思路\n",
    "        n, n_s = len(target), len(stamp)\n",
    "        cnt = 0\n",
    "        tar = list(target)\n",
    "\n",
    "        def match(idx):\n",
    "            ret, c = 0, 0\n",
    "            for i in range(n_s):\n",
    "                if idx + i >= n: break\n",
    "                if tar[idx + i] != '?': c += 1\n",
    "                if tar[idx + i] != '?' and tar[idx + i] != stamp[i]: break\n",
    "                ret += 1\n",
    "            return ret == n_s and c\n",
    "\n",
    "        q = [i for i in range(n - n_s + 1) if match(i)]\n",
    "        ans = []\n",
    "        while q:\n",
    "            for v in q:\n",
    "                ans.append(v)\n",
    "                for i in range(n_s):\n",
    "                    if tar[v + i] != '?':\n",
    "                        cnt += 1\n",
    "                    tar[v + i] = '?'\n",
    "            q = [i for i in range(n - n_s + 1) if match(i)]\n",
    "\n",
    "        return ans[::-1] if cnt == n else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        stamp = list(stamp)\n",
    "        target = list(target)\n",
    "        covered = 0\n",
    "        operations = []\n",
    "        while covered < len(target):\n",
    "            beg = self.firstMatch(stamp, target)\n",
    "            if beg < 0: return []\n",
    "            operations.append(beg)\n",
    "            covered += self.coverMatch(target, beg, beg + len(stamp))\n",
    "        operations.reverse()\n",
    "        return operations\n",
    "        \n",
    "    def firstMatch(self, stamp, target): # 暴力匹配算法，应该还可以优化\n",
    "        for i in range(len(target)-len(stamp)+1):\n",
    "            matching = 0\n",
    "            for j in range(len(stamp)):\n",
    "                c = target[i+j]\n",
    "                if c == '?':\n",
    "                    pass          # old match\n",
    "                elif c == stamp[j]:\n",
    "                    matching = 1  # has new match\n",
    "                else:\n",
    "                    matching = -1\n",
    "                    break         # match failed\n",
    "            if matching > 0:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "    def coverMatch(self, target, beg, end):\n",
    "        covered = 0\n",
    "        for i in range(beg, end):\n",
    "            if target[i] != '?':\n",
    "                target[i] = '?'\n",
    "                covered += 1\n",
    "        return covered"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        m, n = len(stamp), len(target)\n",
    "        if m > n: return []\n",
    "        \n",
    "        t = list(target)\n",
    "        \n",
    "        def check(i):\n",
    "            return ''.join(t[i:i+m]) != '?' * m and all(a == b or b == '?' for a, b in zip(stamp, t[i:i+m]))\n",
    "\n",
    "        ans = []\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            flag = False\n",
    "            for i in range(n - m + 1):\n",
    "                if check(i):\n",
    "                    flag = True\n",
    "                    cnt += 1\n",
    "                    ans.append(i)\n",
    "                    t[i:i+m] = ['?'] * m \n",
    "            if cnt >= 10 * n or ''.join(t) == '?' * n:\n",
    "                break\n",
    "            if flag == False:\n",
    "                break\n",
    "        # print(t, ans)\n",
    "        return ans[::-1] if ''.join(t) == '?' * n else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        q = deque([(0, target, ())])\n",
    "        n = len(target)\n",
    "        m = len(stamp)\n",
    "\n",
    "        raw = '?' * n\n",
    "\n",
    "        def check(x, i):\n",
    "            j = 0\n",
    "            c = 0\n",
    "            for i in range(i, i + m):\n",
    "                if x[i] == stamp[j]:\n",
    "                    j += 1\n",
    "                elif x[i] == '?':\n",
    "                    j += 1\n",
    "                    c += 1\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            return c < m\n",
    "\n",
    "        while q:\n",
    "            t, x, p = q.popleft()\n",
    "\n",
    "            if x == raw:\n",
    "                return p\n",
    "\n",
    "            for i in range(n - m + 1):\n",
    "                if check(x, i):\n",
    "                    q.append((t + 1, x[:i] + '?' * m + x[i + m:], (i,) + p))\n",
    "                    break\n",
    "\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        #逆推，对target不断翻转，直到不会再有变化\n",
    "        m = len(stamp)\n",
    "        n = len(target)\n",
    "        s = list(stamp)\n",
    "        t = list(target)\n",
    "        res = []\n",
    "        change = True\n",
    "\n",
    "        def check(i):\n",
    "            change = False\n",
    "            for j in range(m):\n",
    "                if t[i+j] == '?':\n",
    "                    continue\n",
    "                if t[i+j] != s[j]:\n",
    "                    return False\n",
    "                change = True\n",
    "            if change:\n",
    "                t[i:i+m] = ['?'] * m\n",
    "                res.append(i)\n",
    "            return change\n",
    "        \n",
    "        while change:\n",
    "            change = False\n",
    "            for i in range(n-m+1):\n",
    "                change |= check(i)\n",
    "\n",
    "        return res[::-1] if t.count('?') == n else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        vis=set()\n",
    "        n=len(stamp)\n",
    "       \n",
    "        vis.add(stamp)\n",
    "     \n",
    "        ans=[]\n",
    "        m=len(target)\n",
    "        ans=[]\n",
    "        t=\"?\"*m \n",
    "        #print(vis)\n",
    "        while target!=t:\n",
    "            f=0\n",
    "          #  print(target)\n",
    "            for i in range(m-n+1):\n",
    "                tmp=target[i:i+n]\n",
    "                #print(tmp)\n",
    "                if tmp in vis:\n",
    "                    f=1\n",
    "                    target=target[:i]+\"?\"*n+target[i+n:] \n",
    "                    ans.append(i)\n",
    "        \n",
    "                else:\n",
    "                    j=0\n",
    "                    while j<len(tmp) and tmp[j]==\"?\":\n",
    "                        j=j+1\n",
    "                    k=len(tmp)-1\n",
    "                    while k >=0 and tmp[k]==\"?\":\n",
    "                        k=k-1\n",
    "                    if j!=len(tmp):\n",
    "                        newtmp=tmp[j:k+1]\n",
    "                        if newtmp == stamp[j:k+1]:\n",
    "                            f=1\n",
    "                            target=target[:i]+\"?\"*n+target[i+n:] \n",
    "                            ans.append(i)\n",
    "                            vis.add(tmp)\n",
    "                           \n",
    "\n",
    "            #for i in range(n-1,-1,-1):\n",
    "            #    if target[:i+1]==stamp[n-i-1:]:\n",
    "             #       target=\"?\"*(i+1)+target[i+1:]\n",
    "              #      ans.append(i)\n",
    "              #      break\n",
    "           # for i in range(m-n,m):\n",
    "              #  if target[i:]==stamp[:m-i]:\n",
    "              #      target=target[:i]+\"?\"*(m-i)\n",
    "                 #   ans.append(i)\n",
    "                  #  break\n",
    "            if f==0:\n",
    "                return []\n",
    "                break\n",
    "\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        q = deque([(target, ())])\n",
    "        n = len(target)\n",
    "        m = len(stamp)\n",
    "\n",
    "        raw = '?' * n\n",
    "\n",
    "        def check(x, i):\n",
    "            j = 0\n",
    "            c = 0\n",
    "            for i in range(i, i + m):\n",
    "                if x[i] == stamp[j]:\n",
    "                    j += 1\n",
    "                elif x[i] == '?':\n",
    "                    j += 1\n",
    "                    c += 1\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            return c < m\n",
    "\n",
    "        while q:\n",
    "            x, p = q.popleft()\n",
    "\n",
    "            if x == raw:\n",
    "                return p\n",
    "\n",
    "            for i in range(n - m + 1):\n",
    "                if check(x, i):\n",
    "                    q.append((x[:i] + '?' * m + x[i + m:], (i,) + p))\n",
    "                    break\n",
    "\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        lst = list(target) # 注意python的字符串不能直接改，转为字符列表\n",
    "\n",
    "        def check(p): # 有效的条件，要么已经是问号，要么就能匹配上\n",
    "            return all(lst[p+j]==\"?\" or lst[p+j]==stamp[j] for j in range(len(stamp)))\n",
    "\n",
    "        res = []\n",
    "        st = set() # 哈希集合版的res，避免重复操作相同位置\n",
    "        while True:\n",
    "            for p in range(len(lst)-len(stamp)+1):\n",
    "                if p not in st and check(p):\n",
    "                    for j in range(p,p+len(stamp)):\n",
    "                        lst[j]=\"?\"\n",
    "                    res.append(p)\n",
    "                    st.add(p)\n",
    "                    break # 找到就进入下一次遍历\n",
    "            else: # 找不到就可以返回答案了\n",
    "                return res[::-1] if lst==[\"?\"]*len(lst) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        lst = list(target)\n",
    "        n = len(lst)\n",
    "        lt = len(stamp)\n",
    "        \n",
    "        def check(p):\n",
    "            return all(lst[p+j]==\"?\" or lst[p+j]==stamp[j] for j in range(lt))\n",
    "\n",
    "        res = []\n",
    "        st = set()\n",
    "        while True:\n",
    "            for p in range(n-lt+1):\n",
    "                if p not in st and check(p):\n",
    "                    for j in range(p,p+lt):\n",
    "                        lst[j]=\"?\"\n",
    "                    res.append(p)\n",
    "                    st.add(p)\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return res[::-1] if lst==[\"?\"]*n else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        lst = list(target) # 注意python的字符串不能直接改，转为字符列表\n",
    "\n",
    "        def check(p): # 有效的条件，要么已经是问号，要么就能匹配上\n",
    "            return all(lst[p+j]==\"?\" or lst[p+j]==stamp[j] for j in range(len(stamp)))\n",
    "\n",
    "        res = []\n",
    "        st = set() # 哈希集合版的res，避免重复操作相同位置\n",
    "        while True:\n",
    "            for p in range(len(lst)-len(stamp)+1):\n",
    "                if p not in st and check(p):\n",
    "                    for j in range(p,p+len(stamp)):\n",
    "                        lst[j]=\"?\"\n",
    "                    res.append(p)\n",
    "                    st.add(p)\n",
    "                    break # 找到就进入下一次遍历\n",
    "            else: # 找不到就可以返回答案了\n",
    "                return res[::-1] if lst==[\"?\"]*len(lst) else []\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        lst = list(target)\n",
    "\n",
    "        def check(p):\n",
    "            return all(lst[p+j]==\"?\" or lst[p+j]==stamp[j] for j in range(len(stamp))) and any(lst[p+j]!=\"?\" for j in range(len(stamp)))\n",
    "\n",
    "        res = []\n",
    "        while True:\n",
    "            for p in range(len(lst)-len(stamp)+1):\n",
    "                if check(p):\n",
    "                    for j in range(p,p+len(stamp)):\n",
    "                        lst[j]=\"?\"\n",
    "                    res.append(p)\n",
    "                    break\n",
    "            else:\n",
    "                return res[::-1] if lst==[\"?\"]*len(lst) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        lst = list(target)\n",
    "\n",
    "        def check(p):\n",
    "            return all(lst[p+j]==\"?\" or lst[p+j]==stamp[j] for j in range(len(stamp)))\n",
    "\n",
    "        res = []\n",
    "        st = set()\n",
    "        while True:\n",
    "            for p in range(len(lst)-len(stamp)+1):\n",
    "                if p not in st and check(p):\n",
    "                    for j in range(p,p+len(stamp)):\n",
    "                        lst[j]=\"?\"\n",
    "                    res.append(p)\n",
    "                    st.add(p)\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return res[::-1] if lst==[\"?\"]*len(lst) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        def get_cnt(s):\n",
    "            cnt = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == '?' or s[i] == stamp[i]:\n",
    "                    cnt += s[i] == stamp[i]\n",
    "                else:\n",
    "                    cnt = 0\n",
    "                    break\n",
    "            return cnt \n",
    "        n = len(target)\n",
    "        target = list(target)\n",
    "        res = []\n",
    "        cnt = 0\n",
    "        while cnt < len(target):\n",
    "            for i in range(n - len(stamp) + 1):\n",
    "                nc = get_cnt(target[i : i + len(stamp)])\n",
    "                if nc > 0:\n",
    "                    cnt += nc \n",
    "                    res.append(i)\n",
    "                    target[i : i + len(stamp)] = '?' * len(stamp)\n",
    "                    break \n",
    "            else:\n",
    "                return []\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        vis=set()\n",
    "        n=len(stamp)\n",
    "       \n",
    "        vis.add(stamp)\n",
    "     \n",
    "        ans=[]\n",
    "        m=len(target)\n",
    "        ans=[]\n",
    "        t=\"?\"*m \n",
    "        print(vis)\n",
    "        while target!=t:\n",
    "            f=0\n",
    "            print(target)\n",
    "            for i in range(m-n+1):\n",
    "                tmp=target[i:i+n]\n",
    "                #print(tmp)\n",
    "                if tmp in vis:\n",
    "                    f=1\n",
    "                    target=target[:i]+\"?\"*n+target[i+n:] \n",
    "                    ans.append(i)\n",
    "                    break\n",
    "                else:\n",
    "                    j=0\n",
    "                    while j<len(tmp) and tmp[j]==\"?\":\n",
    "                        j=j+1\n",
    "                    k=len(tmp)-1\n",
    "                    while k >=0 and tmp[k]==\"?\":\n",
    "                        k=k-1\n",
    "                    if j!=len(tmp):\n",
    "                        newtmp=tmp[j:k+1]\n",
    "                        \n",
    "                        if newtmp == stamp[j:k+1]:\n",
    "                            f=1\n",
    "                            target=target[:i]+\"?\"*n+target[i+n:] \n",
    "                            ans.append(i)\n",
    "                            vis.add(tmp)\n",
    "                            break\n",
    "\n",
    "            #for i in range(n-1,-1,-1):\n",
    "            #    if target[:i+1]==stamp[n-i-1:]:\n",
    "             #       target=\"?\"*(i+1)+target[i+1:]\n",
    "              #      ans.append(i)\n",
    "              #      break\n",
    "           # for i in range(m-n,m):\n",
    "              #  if target[i:]==stamp[:m-i]:\n",
    "              #      target=target[:i]+\"?\"*(m-i)\n",
    "                 #   ans.append(i)\n",
    "                  #  break\n",
    "            if f==0:\n",
    "                return []\n",
    "                break\n",
    "\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        lst = list(target)\n",
    "\n",
    "        def check(p):\n",
    "            return all(lst[p+j]==\"?\" or lst[p+j]==stamp[j] for j in range(len(stamp)))\n",
    "\n",
    "        res = []\n",
    "        st = set()\n",
    "        while True:\n",
    "            for p in range(len(lst)-len(stamp)+1):\n",
    "                if p not in st and check(p):\n",
    "                    for j in range(p,p+len(stamp)):\n",
    "                        lst[j]=\"?\"\n",
    "                    res.append(p)\n",
    "                    st.add(p)\n",
    "                    break\n",
    "            else:\n",
    "                return res[::-1] if lst==[\"?\"]*len(lst) else []\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        m, n = len(stamp), len(target)\n",
    "        indeg = [m] * (n - m + 1)  # 入度为每个窗口中对应字符不相同的总数\n",
    "        adjList = [[] for _ in range(n)]  # 如果一个滑动窗口的某一个字符与目标字符串不一致，那么我们就连一条边。\n",
    "        queue = deque()\n",
    "        visited = [False] * n\n",
    "\n",
    "        # 窗口id为区间左侧索引\n",
    "        for i in range(n - m + 1):\n",
    "            for j in range(m):\n",
    "                if target[i + j] == stamp[j]:\n",
    "                    indeg[i] -= 1\n",
    "                    if indeg[i] == 0:\n",
    "                        queue.append(i)\n",
    "                else:\n",
    "                    adjList[i + j].append(i)\n",
    "\n",
    "        res = []\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            res.append(cur)\n",
    "            for i in range(m):\n",
    "                if visited[cur + i]:\n",
    "                    continue\n",
    "                visited[cur + i] = True\n",
    "                for next in adjList[cur + i]:\n",
    "                    indeg[next] -= 1\n",
    "                    if indeg[next] == 0:\n",
    "                        queue.append(next)\n",
    "\n",
    "        return res[::-1] if len(res) == n - m + 1 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        m, n = len(stamp), len(target)\n",
    "        indeg = [m] * (n - m + 1)\n",
    "        adjList = [[] for _ in range(n)]\n",
    "        queue = deque()\n",
    "        visited = [False] * n\n",
    "\n",
    "        # 窗口id为区间左侧索引\n",
    "        for i in range(n - m + 1):\n",
    "            for j in range(m):\n",
    "                if target[i + j] == stamp[j]:\n",
    "                    indeg[i] -= 1\n",
    "                    if indeg[i] == 0:\n",
    "                        queue.append(i)\n",
    "                else:\n",
    "                    adjList[i + j].append(i)  # 如果i+j位置的字符被染色，那么i位置的字符也会被染色\n",
    "\n",
    "        res = []\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            res.append(cur)\n",
    "            for i in range(m):\n",
    "                if visited[cur + i]:\n",
    "                    continue\n",
    "                visited[cur + i] = True\n",
    "                for next in adjList[cur + i]:\n",
    "                    indeg[next] -= 1\n",
    "                    if indeg[next] == 0:\n",
    "                        queue.append(next)\n",
    "\n",
    "        return res[::-1] if len(res) == n - m + 1 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        s = list(stamp)\n",
    "        t = list(target)\n",
    "        m, n = len(s), len(t)\n",
    "\n",
    "        # 入度表，初始值都为 m\n",
    "        indegree = [m] * (n - m + 1)\n",
    "\n",
    "        # 邻接表，用于记录错误位置的关系\n",
    "        graph = [[] for _ in range(n)]\n",
    "\n",
    "        # 用于广度优先搜索的队列\n",
    "        queue = deque()\n",
    "\n",
    "        # 遍历目标字符串\n",
    "        for i in range(n - m + 1):\n",
    "            for j in range(m):\n",
    "                # 如果对应位置相等，说明可以取消错误\n",
    "                if t[i + j] == s[j]:\n",
    "                    # 如果入度大于 0，说明还没取消错误，减少入度\n",
    "                    if indegree[i] > 0:\n",
    "                        indegree[i] -= 1\n",
    "                        # 如果减少后入度为 0，加入队列\n",
    "                        if indegree[i] == 0:\n",
    "                            queue.append(i)\n",
    "                else:\n",
    "                    # 如果不相等，记录错误的位置\n",
    "                    graph[i + j].append(i)\n",
    "\n",
    "        # 记录节点是否被访问过\n",
    "        visited = [False] * n\n",
    "\n",
    "        # 记录拓扑排序的结果\n",
    "        path = []\n",
    "\n",
    "        # 广度优先搜索\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            path.append(cur)\n",
    "            for i in range(m):\n",
    "                if not visited[cur + i]:\n",
    "                    visited[cur + i] = True\n",
    "                    for nxt in graph[cur + i]:\n",
    "                        # 如果入度大于 0，说明还没取消错误，减少入度\n",
    "                        if indegree[nxt] > 0:\n",
    "                            indegree[nxt] -= 1\n",
    "                            # 如果减少后入度为 0，加入队列\n",
    "                            if indegree[nxt] == 0:\n",
    "                                queue.append(nxt)\n",
    "\n",
    "        # 如果拓扑排序的结果数量不等于 n - m + 1，说明有环，返回空数组\n",
    "        if len(path) != n - m + 1:\n",
    "            return []\n",
    "\n",
    "        # 返回拓扑排序的结果（逆序）\n",
    "        return path[::-1]\n",
    "\n",
    "# 测试\n",
    "solution = Solution()\n",
    "stamp = \"abc\"\n",
    "target = \"ababc\"\n",
    "result = solution.movesToStamp(stamp, target)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        m, n = len(stamp), len(target)\n",
    "        inDegree = [m] * (n - m + 1)\n",
    "        edges = [list() for _ in range(n)]\n",
    "        seen = [False] * n\n",
    "        q = list()\n",
    "        for i in range(n - m + 1):\n",
    "            for j in range(m):\n",
    "                if target[i + j] == stamp[j]:\n",
    "                    inDegree[i] -= 1\n",
    "                    if inDegree[i] == 0:\n",
    "                        q.append(i)\n",
    "                else:\n",
    "                    edges[i + j].append(i)\n",
    "        ans = list()\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            ans.append(cur)\n",
    "            for i in range(m):\n",
    "                if not seen[cur + i]:\n",
    "                    seen[cur + i] = True\n",
    "                    for edge in edges[cur + i]:\n",
    "                        inDegree[edge] -= 1\n",
    "                        if inDegree[edge] == 0:\n",
    "                            q.append(edge)\n",
    "        return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        # m, n = len(stamp), len(target)\n",
    "        # inDegree = [m] * (n - m + 1)\n",
    "        # edges = [list() for _ in range(n)]\n",
    "        # seen = [False] * n\n",
    "        # q = list()\n",
    "        # for i in range(n - m + 1):\n",
    "        #     for j in range(m):\n",
    "        #         if target[i + j] == stamp[j]:\n",
    "        #             inDegree[i] -= 1\n",
    "        #             if inDegree[i] == 0:\n",
    "        #                 q.append(i)\n",
    "        #         else:\n",
    "        #             edges[i + j].append(i)\n",
    "        # ans = list()\n",
    "        # while q:\n",
    "        #     cur = q.pop()\n",
    "        #     ans.append(cur)\n",
    "        #     for i in range(m):\n",
    "        #         if not seen[cur + i]:\n",
    "        #             seen[cur + i] = True\n",
    "        #             for edge in edges[cur + i]:\n",
    "        #                 inDegree[edge] -= 1\n",
    "        #                 if inDegree[edge] == 0:\n",
    "        #                     q.append(edge)\n",
    "        # return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n",
    "\n",
    "        m,n = len(stamp),len(target)\n",
    "        degree = [m]*(n-m+1)\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        \n",
    "        queue = []\n",
    "\n",
    "        for i in range(n-m+1):\n",
    "            for j in range(m):\n",
    "                if target[i+j] == stamp[j]:\n",
    "                    degree[i] -= 1\n",
    "                    if degree[i] == 0:\n",
    "                        queue.append(i)\n",
    "\n",
    "                else:\n",
    "                    g[i+j].append(i)\n",
    "        ans = list()\n",
    "        seen = [False] * n\n",
    " \n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for j in range(m):\n",
    "                if not seen[cur + j]:\n",
    "                    seen[cur + j] = True\n",
    "                    for e in g[cur+j]:\n",
    "                        degree[e] -= 1\n",
    "                        if degree[e] == 0:\n",
    "                            queue.append(e) \n",
    "        # print(ans)\n",
    "        return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        m, n = len(stamp), len(target)\n",
    "        inDegree = [m] * (n - m + 1)\n",
    "        edges = [list() for _ in range(n)]\n",
    "        seen = [False] * n\n",
    "        q = list()\n",
    "        for i in range(n - m + 1):\n",
    "            for j in range(m):\n",
    "                if target[i + j] == stamp[j]:\n",
    "                    inDegree[i] -= 1\n",
    "                    if inDegree[i] == 0:\n",
    "                        q.append(i)\n",
    "                else:\n",
    "                    edges[i + j].append(i)\n",
    "        ans = list()\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            ans.append(cur)\n",
    "            for i in range(m):\n",
    "                if not seen[cur + i]:\n",
    "                    seen[cur + i] = True\n",
    "                    for edge in edges[cur + i]:\n",
    "                        inDegree[edge] -= 1\n",
    "                        if inDegree[edge] == 0:\n",
    "                            q.append(edge)\n",
    "        return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n",
    "\n",
    "        # m,n = len(stamp),len(target)\n",
    "        # degree = [m]*(n-m+1)\n",
    "\n",
    "        # g = [[] for _ in range(n)]\n",
    "\n",
    "        \n",
    "        # queue = []\n",
    "\n",
    "        # for i in range(n-m+1):\n",
    "        #     for j in range(m):\n",
    "        #         if target[i+j] == stamp[j]:\n",
    "        #             degree[i] -= 1\n",
    "        #             if degree[i] == 0:\n",
    "        #                 queue.append(i)\n",
    "\n",
    "        #         else:\n",
    "        #             g[i+j].append(i)\n",
    "        # ans = list()\n",
    "        # seen = [False] * n\n",
    " \n",
    "        # while queue:\n",
    "        #     cur = queue.pop()\n",
    "        #     ans.append(cur)\n",
    "\n",
    "        #     for j in range(m):\n",
    "        #         if not seen[cur + j]:\n",
    "        #             seen[cur + j] = True\n",
    "        #         for e in g[cur+j]:\n",
    "        #             degree[e] -= 1\n",
    "        #             if degree[e] == 0:\n",
    "        #                 queue.append(e) \n",
    "        # # print(ans)\n",
    "        # return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        m = len(stamp)\n",
    "        n = len(target)\n",
    "        indegree = [m] * (n-m+1) \n",
    "        quene = [0] * (n-m+1)\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for i in range(n-m+1):\n",
    "            for j in range(m):\n",
    "                if stamp[j] == target[i+j]:\n",
    "                    indegree[i] -= 1\n",
    "                    if indegree[i] == 0:\n",
    "                        quene[r] = i\n",
    "                        r += 1\n",
    "                else:\n",
    "                    graph[i+j].append(i)\n",
    "        visited = [False for _ in range(n)]\n",
    "        ans = [-1 for _ in range(n-m+1)]\n",
    "        cnt = 0\n",
    "        while l < r:\n",
    "            cur = quene[l]\n",
    "            l += 1\n",
    "            ans[cnt] = cur\n",
    "            cnt += 1\n",
    "            for k in range(m):\n",
    "                if not visited[cur+k]:\n",
    "                    visited[cur+k] = True\n",
    "                    for next in graph[cur+k]:\n",
    "                        indegree[next] -= 1\n",
    "                        if indegree[next] == 0:\n",
    "                            quene[r] = next\n",
    "                            r += 1\n",
    "        return quene[::-1] if cnt == n - m + 1 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        m, n = len(stamp), len(target)\n",
    "        inDegree = [m] * (n - m + 1)\n",
    "        edges = [list() for _ in range(n)]\n",
    "        seen = [False] * n\n",
    "        q = list()\n",
    "        for i in range(n - m + 1):\n",
    "            for j in range(m):\n",
    "                if target[i + j] == stamp[j]:\n",
    "                    inDegree[i] -= 1\n",
    "                    if inDegree[i] == 0:\n",
    "                        q.append(i)\n",
    "                else:\n",
    "                    edges[i + j].append(i)\n",
    "        ans = list()\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            ans.append(cur)\n",
    "            for i in range(m):\n",
    "                if not seen[cur + i]:\n",
    "                    seen[cur + i] = True\n",
    "                    for edge in edges[cur + i]:\n",
    "                        inDegree[edge] -= 1\n",
    "                        if inDegree[edge] == 0:\n",
    "                            q.append(edge)\n",
    "        return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        m, n = len(stamp), len(target)\n",
    "        if m > n: return []\n",
    "        ind = [0] * (n - m + 1)\n",
    "        q = []\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(n - m + 1):\n",
    "            for j in range(m):\n",
    "                # print(target[i+j], stamp[i])\n",
    "                if target[i + j] != stamp[j]:\n",
    "                    ind[i] += 1\n",
    "                # else:\n",
    "                    g[i + j].append(i)\n",
    "            if ind[i] == 0:\n",
    "                q.append(i)\n",
    "        # print(ind)\n",
    "        print(q)\n",
    "        f = [False] * n\n",
    "        ans = []\n",
    "        while q:\n",
    "            x = q.pop()\n",
    "            ans.append(x)\n",
    "            for i in range(m):\n",
    "                if not f[x + i]:\n",
    "                    f[x + i] = True\n",
    "                    for y in g[x + i]:\n",
    "                        if ind[y] <= 0: continue\n",
    "                        ind[y] -= 1\n",
    "                        if ind[y] == 0:\n",
    "                            q.append(y)\n",
    "        return ans[::-1] if all(x for x in f) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        m,n=len(stamp),len(target)\n",
    "        deg=[m]*(n-m+1)\n",
    "        e=collections.defaultdict(list)\n",
    "        find=[False]*n\n",
    "        q=[]\n",
    "        for i in range(n-m+1):\n",
    "            for j in range(m):\n",
    "                if target[i+j]==stamp[j]:\n",
    "                    deg[i]-=1\n",
    "                    if deg[i]==0:\n",
    "                        q.append(i)\n",
    "                else:\n",
    "                    e[i+j].append(i)\n",
    "        ans=[]\n",
    "        while q:\n",
    "            now=q.pop()\n",
    "            ans.append(now)\n",
    "            for i in range(m):\n",
    "                if not find[now+i]:\n",
    "                    find[now+i]=True\n",
    "                    for j in e[now+i]:\n",
    "                        deg[j]-=1\n",
    "                        if deg[j]==0:\n",
    "                            q.append(j)\n",
    "        if len(ans)==n-m+1:\n",
    "            return ans[::-1]\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        # m, n = len(stamp), len(target)\n",
    "        # inDegree = [m] * (n - m + 1)\n",
    "        # edges = [list() for _ in range(n)]\n",
    "        # seen = [False] * n\n",
    "        # q = list()\n",
    "        # for i in range(n - m + 1):\n",
    "        #     for j in range(m):\n",
    "        #         if target[i + j] == stamp[j]:\n",
    "        #             inDegree[i] -= 1\n",
    "        #             if inDegree[i] == 0:\n",
    "        #                 q.append(i)\n",
    "        #         else:\n",
    "        #             edges[i + j].append(i)\n",
    "        # ans = list()\n",
    "        # while q:\n",
    "        #     cur = q.pop()\n",
    "        #     ans.append(cur)\n",
    "        #     for i in range(m):\n",
    "        #         if not seen[cur + i]:\n",
    "        #             seen[cur + i] = True\n",
    "        #             for edge in edges[cur + i]:\n",
    "        #                 inDegree[edge] -= 1\n",
    "        #                 if inDegree[edge] == 0:\n",
    "        #                     q.append(edge)\n",
    "        # return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n",
    "\n",
    "        m,n = len(stamp),len(target)\n",
    "        degree = [m]*(n-m+1)\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        \n",
    "        queue = []\n",
    "\n",
    "        for i in range(n-m+1):\n",
    "            for j in range(m):\n",
    "                if target[i+j] == stamp[j]:\n",
    "                    degree[i] -= 1\n",
    "                    if degree[i] == 0:\n",
    "                        queue.append(i)\n",
    "\n",
    "                else:\n",
    "                    g[i+j].append(i)\n",
    "        ans = list()\n",
    "        seen = [False] * n\n",
    "        # print(degree,g,queue)\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            ans.append(cur)\n",
    "\n",
    "            for j in range(m):\n",
    "                if not seen[cur + j]:\n",
    "                    seen[cur + j] = True\n",
    "                    for e in g[cur+j]:\n",
    "                        degree[e] -= 1\n",
    "                        if degree[e] == 0:\n",
    "                            queue.append(e) \n",
    "            print(queue)\n",
    "        # print(ans)\n",
    "        return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "\n",
    "        # m, n = len(stamp), len(target)\n",
    "        # inDegree = [m] * (n - m + 1)\n",
    "        # edges = [list() for _ in range(n)]\n",
    "        # seen = [False] * n\n",
    "        # q = list()\n",
    "        # for i in range(n - m + 1):\n",
    "        #     for j in range(m):\n",
    "        #         if target[i + j] == stamp[j]:\n",
    "        #             inDegree[i] -= 1\n",
    "        #             if inDegree[i] == 0:\n",
    "        #                 q.append(i)\n",
    "        #         else:\n",
    "        #             edges[i + j].append(i)\n",
    "        # ans = list()\n",
    "        # while q:\n",
    "        #     cur = q.pop()\n",
    "        #     ans.append(cur)\n",
    "        #     for i in range(m):\n",
    "        #         if not seen[cur + i]:\n",
    "        #             seen[cur + i] = True\n",
    "        #             for edge in edges[cur + i]:\n",
    "        #                 inDegree[edge] -= 1\n",
    "        #                 if inDegree[edge] == 0:\n",
    "        #                     q.append(edge)\n",
    "        # return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n",
    "\n",
    "        m,n = len(stamp),len(target)\n",
    "        degree = [m]*(n-m+1)\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        \n",
    "        queue = []\n",
    "\n",
    "        for i in range(n-m+1):\n",
    "            for j in range(m):\n",
    "                if target[i+j] == stamp[j]:\n",
    "                    degree[i] -= 1\n",
    "                    if degree[i] == 0:\n",
    "                        queue.append(i)\n",
    "\n",
    "                else:\n",
    "                    g[i+j].append(i)#存起点\n",
    "        ans = list()\n",
    "        seen = [False] * n\n",
    "        # print(degree,g,queue)\n",
    "        while queue:\n",
    "            cur = queue.pop()\n",
    "            ans.append(cur)\n",
    "            for j in range(m):\n",
    "                if not seen[cur + j]:#cur+j这些点不可能作为起点了，和这些点相关的起点的度需要-1\n",
    "                    seen[cur + j] = True\n",
    "                    for e in g[cur+j]:\n",
    "                        degree[e] -= 1\n",
    "                        if degree[e] == 0:\n",
    "                            queue.append(e) \n",
    "            print(queue)\n",
    "        # print(ans)\n",
    "        return ans[::-1] if len(ans) == n - m + 1 else list()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        m, n = len(stamp), len(target)\n",
    "        child_dict = defaultdict(set)\n",
    "        parent_dict = defaultdict(list)\n",
    "        ans = []\n",
    "        for i in range(n - m + 1):\n",
    "            for j in range(m):\n",
    "                if target[i + j] != stamp[j]:\n",
    "                    child_dict[i].add(i + j)\n",
    "                    parent_dict[i + j].append(i)\n",
    "        queue = deque()\n",
    "        for i in range(n - m + 1):\n",
    "            if i not in child_dict:\n",
    "                queue.append(i)\n",
    "        complete = set()\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            ans.append(cur)\n",
    "            for i in range(cur, cur + m):\n",
    "                if i in complete:\n",
    "                    continue\n",
    "                complete.add(i)\n",
    "                for parent in parent_dict[i]:\n",
    "                    child_dict[parent].remove(i)\n",
    "                    if len(child_dict[parent]) == 0:\n",
    "                        queue.append(parent)\n",
    "            if len(complete) == n:\n",
    "                return ans[::-1]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        M, N = len(stamp), len(target)\n",
    "\n",
    "        queue = deque()\n",
    "        done = [False]*N\n",
    "        ans = []\n",
    "        A = []\n",
    "\n",
    "        for i in range(N-M+1):\n",
    "            made, todo = set(),set()\n",
    "            for j,c in enumerate(stamp):\n",
    "                if c == target[i+j]:\n",
    "                    made.add(i+j)\n",
    "                else:\n",
    "                    todo.add(i+j)\n",
    "            A.append((made, todo))\n",
    "        \n",
    "            if len(todo)==0:\n",
    "                ans.append(i)\n",
    "                for j in range(i, i+len(stamp)):\n",
    "                    if not done[j]:\n",
    "                        queue.append(j)\n",
    "                        done[j] = True\n",
    "        \n",
    "        while queue:\n",
    "            i = queue.popleft()\n",
    "\n",
    "            for j in range(max(0,i-M+1), min(N-M, i)+1):\n",
    "                if i in A[j][1]:\n",
    "                    A[j][1].discard(i)\n",
    "                    if len(A[j][1])==0:\n",
    "                        ans.append(j)\n",
    "                        for m in A[j][0]:\n",
    "                            if not done[m]:\n",
    "                                queue.append(m)\n",
    "                                done[m] = True\n",
    "        return ans[::-1] if all(done) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def movesToStamp(self, stamp, target):\n",
    "        M, N = len(stamp), len(target)\n",
    "\n",
    "        queue = collections.deque()\n",
    "        done = [False] * N\n",
    "        ans = []\n",
    "        A = []\n",
    "        for i in range(N - M + 1):\n",
    "            # For each window [i, i+M),\n",
    "            # A[i] will contain info on what needs to change\n",
    "            # before we can reverse stamp at i.\n",
    "\n",
    "            made, todo = set(), set()\n",
    "            for j, c in enumerate(stamp):\n",
    "                a = target[i+j]\n",
    "                if a == c:\n",
    "                    made.add(i+j)\n",
    "                else:\n",
    "                    todo.add(i+j)\n",
    "            A.append((made, todo))\n",
    "\n",
    "            # If we can reverse stamp at i immediately,\n",
    "            # enqueue letters from this window.\n",
    "            if not todo:\n",
    "                ans.append(i)\n",
    "                for j in range(i, i + len(stamp)):\n",
    "                    if not done[j]:\n",
    "                        queue.append(j)\n",
    "                        done[j] = True\n",
    "\n",
    "        # For each enqueued letter,\n",
    "        while queue:\n",
    "            i = queue.popleft()\n",
    "\n",
    "            # For each window that is potentially affected,\n",
    "            # j: start of window\n",
    "            for j in range(max(0, i-M+1), min(N-M, i)+1):\n",
    "                if i in A[j][1]:  # This window is affected\n",
    "                    A[j][1].discard(i) # Remove it from todo list of this window\n",
    "                    if not A[j][1]:  # Todo list of this window is empty\n",
    "                        ans.append(j)\n",
    "                        for m in A[j][0]: # For each letter to potentially enqueue,\n",
    "                            if not done[m]:\n",
    "                                queue.append(m)\n",
    "                                done[m] = True\n",
    "\n",
    "        return ans[::-1] if all(done) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToStamp(self, stamp: str, target: str) -> List[int]:\n",
    "        M, N = len(stamp), len(target)\n",
    "\n",
    "        queue = collections.deque()\n",
    "        done = [False] * N\n",
    "        ans = []\n",
    "        A = []\n",
    "        for i in range(N - M + 1):\n",
    "            # For each window [i, i+M),\n",
    "            # A[i] will contain info on what needs to change\n",
    "            # before we can reverse stamp at i.\n",
    "\n",
    "            made, todo = set(), set()\n",
    "            for j, c in enumerate(stamp):\n",
    "                a = target[i+j]\n",
    "                if a == c:\n",
    "                    made.add(i+j)\n",
    "                else:\n",
    "                    todo.add(i+j)\n",
    "            A.append((made, todo))\n",
    "\n",
    "            # If we can reverse stamp at i immediately,\n",
    "            # enqueue letters from this window.\n",
    "            if not todo:\n",
    "                ans.append(i)\n",
    "                for j in range(i, i + len(stamp)):\n",
    "                    if not done[j]:\n",
    "                        queue.append(j)\n",
    "                        done[j] = True\n",
    "\n",
    "        # For each enqueued letter,\n",
    "        while queue:\n",
    "            i = queue.popleft()\n",
    "\n",
    "            # For each window that is potentially affected,\n",
    "            # j: start of window\n",
    "            for j in range(max(0, i-M+1), min(N-M, i)+1):\n",
    "                if i in A[j][1]:  # This window is affected\n",
    "                    A[j][1].discard(i) # Remove it from todo list of this window\n",
    "                    if not A[j][1]:  # Todo list of this window is empty\n",
    "                        ans.append(j)\n",
    "                        for m in A[j][0]: # For each letter to potentially enqueue,\n",
    "                            if not done[m]:\n",
    "                                queue.append(m)\n",
    "                                done[m] = True\n",
    "\n",
    "        return ans[::-1] if all(done) else []"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
